package com.lry.basic.algorithm.common;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author:刘仁有
 * @desc:
 * @email:953506233@qq.com
 * @data:2019/10/9
 */

/**
 * 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 * candidates 中的数字可以无限制重复被选取。
 *
 * 说明：
 *     所有数字（包括 target）都是正整数。
 *     解集不能包含重复的组合。
 *
 * 示例 1:
 *
 * 输入: candidates = [2,3,6,7], target = 7,
 * 所求解集为:
 * [
 *   [7],
 *   [2,2,3]
 * ]

 */
public class CombinationSum {

    public static void main(String[] args) {
        CombinationSum cs = new CombinationSum();
        List<List<Integer>> list = cs.combinationSum(new int[]{1,1,2,3},3);
        for(int i=0;i<list.size();i++){
            for(int j=0;j<list.get(i).size();j++){
                System.out.print(list.get(i).get(j)+" ");
            }
            System.out.println();
        }
    }
    List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);//排序加快递归速度
        List<Integer> out = new ArrayList<>();
        backTrack(candidates,0,target,0,out);
        return result;
    }
    //start这个参数去除重复组合 并且加快递归速度  LEETCODE40
    public void backTrack(int[] candidates, int start,int target,int sum,List<Integer> out){
        if(sum==target){//结果集 剪枝
            result.add(new ArrayList<Integer>(out));//这里必须new一个
            return;
        }else{
            for(int i=start;i<candidates.length;i++){
                //肯定不符合，直接break 剪枝
                if (sum + candidates[i] > target) {
                    break;
                }
                // 相同部分剪枝  去重
                if (i > start && candidates[i] == candidates[i - 1]) {
                    continue;
                }

                out.add(candidates[i]);
                sum+=candidates[i];
                backTrack(candidates,i+1,target,sum,out);
                //一轮搜索结束 需要移除最后一个元素
                sum-=candidates[i];
                out.remove(out.size()-1);
            }
        }
    }

//    LEETCODE39
//    public void backTrack(int[] candidates, int start,int target,int sum,List<Integer> out){
//        if(sum==target){//结果集 剪枝
//            result.add(new ArrayList<Integer>(out));//这里必须new一个
//            return;
//        }else{
//            for(int i=start;i<candidates.length;i++){
//                //肯定不符合，直接break 剪枝
//                if (sum + candidates[i] > target) {
//                    break;
//                }
//                out.add(candidates[i]);
//                sum+=candidates[i];
//                backTrack(candidates,i,target,sum,out);
//                //一轮搜索结束 需要移除最后一个元素
//                sum-=candidates[i];
//                out.remove(out.size()-1);
//            }
//        }
//    }

}
